package com.demo.structure.array;

import org.springframework.util.ObjectUtils;

/**
 * 链表
 * 1.链表是以节点的方法来存储，链式存储
 * 2.每个节点包含data域，next域：指向下一个节点
 * 3.链表的各个节点不一定是连续存储
 * 4.链表分带头节点的链表和没有头节点的链表（根据时间需求来确定）
 *
 * @author: 蔡奇峰
 * @date: 2020/7/4 13:52
 **/
public class LinkedList {

    public static void main(String[] args) {
        SingleLinkedList linkedList =  new SingleLinkedList();

        StudentNode tale = new StudentNode(1, "tale");
        StudentNode node = new StudentNode(2, "node");
        StudentNode git = new StudentNode(3, "git");
        StudentNode one = new StudentNode(11, "one");
        StudentNode p = new StudentNode(2, "更新node");

        // 无序添加
//        linkedList.add(tale);
//        linkedList.add(node);
//        linkedList.add(git);

        // 顺序添加
        linkedList.addByOrder(git);
        linkedList.addByOrder(tale);
        linkedList.addByOrder(node);
        linkedList.addByOrder(one);

        linkedList.list();
        linkedList.update(p);

        linkedList.del(11);

        linkedList.addByOrder(git);

        linkedList.list();

        System.out.println("链表反转：");
        linkedList.reverseLinked(linkedList.getHead());

        linkedList.list();

        System.out.println("获取倒数第2个：" + linkedList.findByLastIndex(linkedList.getHead(), 2));
    }


}

/**
 * 单链表
 */
class SingleLinkedList{

    /**
     * 头节点，不存放具体数据
     */
    private StudentNode head = new StudentNode(0, "");

    /**
     * 获取头节点
     *
     * @return
     */
    public StudentNode getHead(){
        return head;
    }



    /**
     * 链表反转
     * 遍历节点，每遍历一个节点，就将其取出，并放在新的链表的最前端。
     *
     * @param head 链表头部
     */
    public void reverseLinked(StudentNode head){
        // 如果链表为空或者只有一个节点，直接返回
        if (head.next == null || head.next.next == null){
            return;
        }
        // 当前需要反转的链表
        StudentNode current = head.next;
        // 一个辅助遍历的节点
        StudentNode temp = null;
        // 头节点
        StudentNode reverseHead = new StudentNode(0, "");

        while (current != null){
            temp = current.next;
            // 最后一个节点实际上是空节点
            current.next = reverseHead.next;
            //
            reverseHead.next = current;
            // 后移
            current = temp;
        }

        head.next = reverseHead.next;

    }


    /**
     * 添加节点
     *
     * @param node
     */
    public void add(StudentNode node){
        // 定义一个临时节点用于辅助遍历
        StudentNode temp = head;
        while (true){
            // 为空则找到链表的尾部
            if (ObjectUtils.isEmpty(temp.next)){
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 按顺序添加（这里既是按学号添加）
     *
     * @param node
     */
    public void addByOrder(StudentNode node){
        // 定义一个临时节点用于辅助遍历
        StudentNode temp = head;
        while (true){
            // 为空则找到链表的尾部
            if (ObjectUtils.isEmpty(temp.next)){
                break;
            }
            // 小的排前面
            if (node.studentNo == temp.next.studentNo){
                System.out.printf("添加失败！添加的学号%d已经存在！", node.studentNo);
                System.out.println();
                break;
            }else if (node.studentNo < temp.next.studentNo){
                node.next = temp.next;
                temp.next = node;
                break;
            }else {

                // 向后移
                temp = temp.next;
            }
        }
        temp.next = node;

    }

    /**
     * 更新
     *
     * @param node
     */
    public void update(StudentNode node){
        // 定义一个临时节点用于辅助遍历
        StudentNode temp = head;
        while (true){
            // 为空则找到链表的尾部
            if (ObjectUtils.isEmpty(temp.next)){
                System.out.println("更新失败!没有找到这个节点");
                break;
            }

            if (node.studentNo == temp.next.studentNo){
                temp.next = node;
                System.out.println("更新成功");
                break;
            }

            // 向后移
            temp = temp.next;

        }
    }

    /**
     * 删除节点
     *
     * @param studentNo
     */
    public void del(int studentNo){
        // 定义一个临时节点用于辅助遍历
        StudentNode temp = head;
        while (true){
            // 为空则已经链表的尾部说明找不到
            if (ObjectUtils.isEmpty(temp.next)){
                System.out.printf("删除失败!没有找到学号%d", studentNo);
                System.out.println();
                break;
            }
            // 找到节点则结束
            if (studentNo == temp.next.studentNo){
                temp.next = temp.next.next;
                System.out.println("删除成功！");
                break;
            }
            // 向后移
            temp = temp.next;

        }

    }

    /**
     * 获取倒数第n个节点
     *
     * @param head 链表头部
     * @param index 倒数第index个节点
     * @return
     */
    public StudentNode findByLastIndex(StudentNode head, int index){
        // 链表为空
        if (head.next == null){
            return null;
        }
        // 获取链表的有效长度
        int length = getLength(head);

        // 链表有效长度 < index 或者有效长度 <= 0
        if (index > length || length <= 0){
            return null;
        }

        StudentNode current = head.next;
        for (int i = 0; i < length - index; i++) {
            current = current.next;
        }
        return current;

    }

    /**
     * 获取链表有效长度
     *
     * @param head 链表头部
     * @return
     */
    public int getLength(StudentNode head){
        if (head.next == null){
            return 0;
        }
        int len = 0;
        StudentNode current = head.next;
        while (current != null){
            len ++;
            current = current.next;
        }

        return len;
    }


    /**
     * 显示链表
     */
    public void list(){
        // 定义一个临时节点用于辅助遍历
        StudentNode temp = head;
        while (true){
            // 为空则找到链表的尾部
            if (ObjectUtils.isEmpty(temp.next)){
                break;
            }
            System.out.println(temp.next.toString());
            temp = temp.next;
        }
    }

}

class StudentNode{

    public int studentNo;
    public String name;

    /**
     * 用于指向下一个节点
     */
    public StudentNode next;


    public StudentNode(int studentNo, String name) {
        this.studentNo = studentNo;
        this.name = name;
    }

    @Override
    public String toString() {
        return "StudentNode{" +
                "studentNo=" + studentNo +
                ", name='" + name + '\'' +
                ", next=" + next +
                '}';
    }
}